Computer-based activities are now subject to electronic vandalism. A vandal, who is sometimes called a hacker in this context, may attempt to intrude upon a computer in order to steal information in an act of industrial espionage, or to alter records to the detriment or the benefit of another party's interests or reputation, or to impede the operation of the computer by implanting a virus or by flooding the computer with bogus information.
Computers are often protected against vandals' intrusions by intrusion detection systems. An intrusion detection system (IDS) monitors the activities of users and would-be users for particular events or patterns of events generally known as signatures. A signature typically includes a signature event, which may be the fingerprint of a sequence of actions that constitute misuse or unauthorized use of the computer. In many instances, a signature event may be a particular pattern of bits. For example, the signature event may be a pattern of bits that identifies an incoming message designed to induce a deliberate violation of a communication protocol, where the kind of violation may be indicative of a potential intrusion.
Signatures, and consequently signature events, are stored in a signature table within or associated with the IDS. In addition to a signature event, a signature in the signature table may include an associated signature event counter for counting the number of times the signature event occurs, and a signature threshold that may be used to differentiate between attempted intrusions and uneventful occurrences of the signature event. For example, the signature event may be required to occur J times in K minutes before an intrusion is suspected. Thus, for example, more than five occurrences in twenty minutes of the signature event “protocol violation 3” may serve as an indicator that an unauthorized party may be attempting to intrude upon the computer protected by the IDS.
When the intrusion detection system observes activity that is suggestive or indicative of an intrusion, for example when the value of a signature event counter crosses its associated signature threshold, the IDS may generate an alert. The purpose of the alert is to inform a network administrator of the intrusion, so that the administrator may act to minimize the damage done by the intruder. The alert may include other information drawn from the particular signature that is associated with the suspected intrusion, such as a priority or importance level suggesting the urgency of the need for defensive action, or instructions or data to help the administrator limit the damage done by the intruder.
One kind of particularly damaging intrusion is called a “denial of service” attack, in which a vandal floods a target computer such as an Internet-connected web server with a torrential flow of disruptive messages that overload the target to the point of functional failure. During a denial of service attack, the vandal may fraudulently assume a number of different electronic identities, often by including messages in the disruptive flow that have a variety of source addresses. Such a vandal is often called a spoofer.
In one kind of denial-of-service attack, a spoofer may send the target a large number of Internet Control Message Protocol (ICMP) messages called Packet INternet Gropers (PING), which are normally used to query whether a particular Internet address is accessible to the sender. Upon receiving a PING packet, the target responds to the spoofed device rather than the vandal, as the PING packet bears the fraudulently used identity of the spoofed device. By flooding the target with PING packets, the vandal may divert the target's resources to generating responses and consequently away from its legitimate tasks, and may also cause unproductive network congestion by triggering a flood of response messages.
In another kind of denial-of-service attack, the vandal may send the target a large number of TCP SYN messages. A TCP SYN message is normally used to initiate a TCP connection. Upon receiving a SYN message, the target sends a SYN/ACK message to the spoofed device rather than the vandal, as the SYN message bears the fraudulently used identity of the spoofed device. Further, the target reserves an internal data structure presumably to be used in supporting a connection with the spoofed device. So, by flooding the target computer with a large number of SYN messages, the vandal causes not only the problems mentioned above—resource diversion and network congestion—but also exhausts the target's capacity to support the data structures needed to establish other connections. Thus, the attack renders the target unable to establish connections with any device except the spoofed device.
Protective equipment may combat such attacks by filtering incoming messages according to information provided by the intrusion detection system. In this case, when the IDS detects the onslaught of a vandal's attack, the IDS reads the source addresses or other markings that the vandal usurps and fraudulently re-uses, and the IDS sends out alerts to inform the network administrator of the attack. The administrator may then configure the filtering equipment to block incoming messages that seem to originate from the malicious source.
To detect an intrusion, the IDS monitors system activity for the occurrence of system events, some of which may be signature events. When an event detector within the IDS detects a system event, logic within the IDS searches the signature table, looking for a signature whose signature event matches the system event. Although each such search may be accomplished easily, the search operation may consume significant resources during periods of intense activity. For example, when a vandal launches an attack that involves an onslaught of incoming messages, as in the case of a typical denial-of-service attack, the logic within the intrusion detection system repeatedly searches the signature table, looking for signature events that match the system events caused by the vandal. More particularly, when the signature table contains N signatures, on average each search of the signature table requires N/2 pattern-matching comparisons to find the signature whose signature event corresponds to the system event. Thus, during periods of intense activity such as a denial of service attack, the performance of the intrusion detection system may be limited to its capability to search the signature list.
Further complicating the situation, and perhaps more importantly, a system event does not always and necessarily indicate an intrusion; in fact, the contrary is normally true. The IDS event detector may routinely detect system events in the course of normal operation of the device protected by the IDS. The mechanism that distinguishes between signature events that pose a threat to the protected device and other system events that do not is the presence or absence of an associated signature in the signature table.
Consequently, the IDS must search its signature table in response to each system event to determine whether an associated signature is present in the signature table or not, and therefore whether the system event is indicative of a potential intrusion or not. However, since the vast majority of system events may pose no threat to the protected device, this kind of fruitless searching increases both system latency and processing load, again in proportion to the length of the signature table. More specifically, when the signature table contains N signatures, each signature-table search in response to detection of a routine system event requires N pattern-matching comparisons to determine that the signature table does not contain a matching signature event, and that the system event is therefore of no interest.
Today, for the reasons just mentioned, the signature-table search operation is time consuming and resource intensive, and promises to become even more so in the future as the sophistication and persistence of vandals increase, thereby necessitating longer signature tables. Thus there is a need for a way of improving the performance of an intrusion detection system, specifically the performance of the IDS signature-table search operation, to minimize system latency, to enable the IDS to provide more responsive defense against acts of vandalism such as denial-of-service attacks, and to ensure that the IDS does not itself become a performance bottleneck.